using System.Collections.Generic;
using Kopernikus.Collections.Generic;
using Kopernikus.Parsing.Utility;

namespace Kopernikus.Parsing.Earley
{
    // Nihilist Normal Form Grammar
    public class NNFGrammar : Grammar
    {
        private NNFGrammar(IGrammar grammar, Dictionary<Production, Production> mappedProductions)
            : base(
                GenerateNNF(grammar, grammar.StartProductions, mappedProductions),
                GenerateNNF(grammar, grammar.Productions, mappedProductions), mappedProductions)
        {
        }

        public NNFGrammar(IGrammar grammar) : this(grammar, new Dictionary<Production, Production>())
        {
        }

        private static Set<Production> GenerateNNF(IGrammar grammar, Set<Production> productions,
                                                   IDictionary<Production, Production> mappedProductions)
        {
            if (grammar.SymbolSets.NullableSymbols.Count == 0)
            {
                return productions;
            }

            Set<Production> newProductions = new Set<Production>();

            Dictionary<Symbol, Symbol> epsilonSymbolMap = new Dictionary<Symbol, Symbol>();
            Set<Symbol> epsilonSymbols = new Set<Symbol>();
            foreach (Symbol symbol in grammar.SymbolSets.NullableSymbols)
            {
                Symbol epsilonSymbol = new Symbol(symbol.Name, SymbolFlags.NNFNullable);
                epsilonSymbolMap.Add(symbol, epsilonSymbol);
                epsilonSymbols.Add(epsilonSymbol);
            }

            foreach (Production p in productions)
            {
                if (p.RHS.Length == 0)
                {
                    Production nullableProduction = new Production(new Symbol[] {epsilonSymbolMap[p.LHS]});
                    mappedProductions[newProductions.Add(nullableProduction)] = p;
                }
                else
                {
                    Combinator<Symbol> combinator = new Combinator<Symbol>();
                    foreach (Symbol s in p.RHS)
                    {
                        if (grammar.SymbolSets.NullableSymbols.Contains(s))
                        {
                            combinator.AddCombinations(s, epsilonSymbolMap[s]);
                        }
                        else
                        {
                            combinator.AddCombinations(s);
                        }
                    }
                    foreach (List<Symbol> symbols in combinator.Combinations)
                    {
                        List<Symbol> newSymbols = new List<Symbol>();
                        if (epsilonSymbols.Contains(symbols))
                        {
                            newSymbols.Add(epsilonSymbolMap[p.LHS]);
                        }
                        else
                        {
                            newSymbols.Add(p.LHS);
                        }
                        newSymbols.AddRange(symbols);
                        Production newProduction = new Production(newSymbols);
                        mappedProductions[newProductions.Add(newProduction)] = p;
                    }
                }
            }
            return newProductions;
        }
    }
}